﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_2055_PlatesBetweenCandles
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[][] array = new int[][] {
                new int[]{1,17 },
                new int[]{4,5 },
                new int[]{14,17 },
                new int[]{5,11 },
                new int[]{15,16 },
            };
            foreach (var item in PlatesBetweenCandles("***|**|*****|**||**|*", array))
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }
        public static int[] PlatesBetweenCandles(string s, int[][] queries)
        {
            #region 前缀和+预处理

            int[] arrL = new int[s.Length];
            int[] arrR = new int[s.Length];
            int[] arr = new int[s.Length];

            int record = 0;
            int num = 0;
            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '|') record = i;
                arrL[i] = record;

                if (s[i] == '|') num++;
                arr[i] = num;
            }

            for (int i = s.Length - 1; i >= 0; i--)
            {
                if (s[i] == '|') record = i;
                arrR[i] = record;
            }
            int[] res = new int[queries.Length];

            for (int i = 0; i < queries.Length; i++)
            {
                int left = arrL[queries[i][1]];
                int right = arrR[queries[i][0]];
                if (left> right)
                {
                    res[i] = (left - right - 1) - (arr[left] - arr[right] - 1);
                }
                else
                {
                    res[i] = 0;
                }
            }
            return res;
            #endregion

            #region 两遍遍历(超时)
            //List<int> allIndex = new List<int>();
            //for (int i = 0; i < s.Length; i++) if (s[i] == '|') allIndex.Add(i);

            //int[] res = new int[queries.Length];
            //int index = 0;
            //foreach (var item in queries)
            //{
            //    int first = 0;
            //    int second = 0;
            //    int sum = 0;
            //    foreach (var l in allIndex)
            //    {
            //        if (item[0] <= l)
            //        {
            //            first = l;
            //            break;
            //        }

            //    }
            //    for (int i = allIndex.Count - 1; i >= 0; i--)
            //    {
            //        if (item[1] >= allIndex[i])
            //        {
            //            second = allIndex[i];
            //            break;
            //        }
            //    }

            //    for (int i = first+1; i < second; i++)
            //    {
            //       if (s[i] == '*') sum++;
            //    }

            //    res[index] = sum;
            //    index++;
            //}
            //return res;

            #endregion

            #region 模拟（可以但超时）
            //int[] res = new int[queries.Length];

            //for (int i = 0; i < queries.Length; i++) HandleData(s, queries[i], res, i);

            //return res;
            #endregion
        }

        private static void HandleData(string s, int[] vs, int[] res, int j)
        {
            string str = s.Substring(vs[0], vs[1] - vs[0] + 1);

            Stack<char> stack = new Stack<char>();

            int sum = 0;

            int firstIndex = 0;
            int secondIndex = 0;

            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] == '|')
                {
                    firstIndex = i;
                    break;
                }
            }

            for (int i = str.Length - 1; i >= 0; i--)
            {
                if (str[i] == '|')
                {
                    secondIndex = i;
                    break;
                }
            }

            for (int i = firstIndex + 1; i < secondIndex; i++)
            {
                if (str[i] == '*')
                {
                    sum++;
                }
            }
            res[j] = sum;
        }
    }
}
